package leetcode.editor.cn;

import leetcode.editor.cn.common.ListNode;

/**
 * @Author: Dempsey
 * @Data: 2021-01-05 15:59:13
 */

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
//
// 
//
// 示例： 
//
// 输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
// 
// Related Topics 递归 链表 
// 👍 1461 👎 0


public class P21 {
    public static void main(String[] args) {
        Solution solution = new P21().new Solution();
        ListNode a = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode b = new ListNode(1, new ListNode(3, new ListNode(4)));
        solution.mergeTwoLists(a, b);
    }

//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode ans = new ListNode(0);
            ListNode head = ans;

            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    head.next = l1;
                    l1 = l1.next;
                } else {
                    head.next = l2;
                    l2 = l2.next;
                }
                head = head.next;
            }

            head.next = l1 == null ? l2 : l1;

            return ans.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}